مقاله40-بررسی و کاربرد هوش ازدحامی در مسئله مدیریت بحران60ص

فهرست مطالب

عنوان صفحه

 

 

فصل اول – مقدمه ............................................................................................................ 1

فصل دوم-مدیریت بحران................................................................................................... 4

2-1-مقدمه ...................................................................................................................... 4

2-2-مدیریت بحران.......................................................................................................... 5

2-3-آژانسهای مدیریت بحران............................................................................................ 8

2-3-1- آژانس مدیریت اضطراری فدرال (FEMA).......................................................... 8

2-3-2-اینفوسفر- سیستم دریافت و پاسخ.................................................................................. 11

2-3-3-سیستم مدیریت بحران (CMS) ...... 12

2-4-انواع روشهای الگوریتمی تخصیص منابع..................................................................... 14

2-4-1-برنامه نویسی پویا.................................................................................................. 14

2-4-2-برنامه نویسی عدد صحیح ...................................................................................... 15

2-4-3-روش ضرب کننده لاگرانژ ..................................................................................... 16

2-4-4-باز پخت شبیه سازی شده ...................................................................................... 18

2-4-5-الگوریتم ژنتیک 19

2-4-6- انشعاب و کران 21

2-4-7- الگوریتم حریص ................................................................................................. 21

2-4-8- جستجوی تابو 22

2-4-9- تئوری بازیها 23

2-5-عملیات نجات روبوکاپ............................................................................................ 23

2-5-1-ساختار سیستم 25

2-5-2-ساختار عاملها 25

2-5-3-تشکیل تیم 27

فصل3 -هوش ازدحامی..................................................................................................... 29

3-1- مقدمه.................................................................................................................... 29

3-2-الگوریتم بهینه سازی کلونی مورچه ها(ACO) ........................................................... 31

3-2-1-مورچه ها چگونه میتوانند کوتاهترین مسیر را پیدا کنند؟.......................................... 32

3-2-2-کاربردهای ACO................................................................................................. 34

3-3- الگوریتم بهینه سازی انبوه ذرات (PSO) ................................................................. 34

3-3-1-الگوریتم pso .................................................................................................... 35

3-3-2 کاربردهای pso ................................................................................................... 37

3-4-الگوریتم ژنتیکGA ................................................................................................ 37

3-4-1- الگوریتم GA..................................................................................................... 38

3-4-2-کاربردهای GA.................................................................................................... 39

فصل چهارم - استفاده از هوش ازدحامی در مدیریت بحران.................................................. 40

4-1-مقدمه 40

4-2-هوش ازدحامی ......................................................................................................... 42

4-3-حوزه مديريت اورژانسي............................................................................................ 44

4-4-روش شناسي............................................................................................................ 46

4-5-مكانيزم های تخصيص كار مرسوم............................................................................... 46

4-6-روند واكنش اورژانسي .............................................................................................. 48

4-7-ساخت و ارزيابي مدل................................................................................................ 49

4-8-روش شبيه سازي ...... 51

4-9-طراحی آزمایشات...................................................................................................... 53

4-10-روش مقایسه مکانیزم............................................................................................... 54

4-11-رتبه بندی................................................................................................................ 55

فصل پنجم-نتیجه گیری و پیشنهادات ................................................................................. 58

منابع ومراجع ................................................................................................................... 61

 

 

 

 

 

 

 

 

 

 

 

 

فهرست شکلها

عنوان صفحه

 

 

شکل 1-وقوع چند بحران هم زمان در یک ناحیه شهری............................................................. 6

شکل 2- FEMA – 101SLG فرایند برنامه ریزی................................................................. 9

شکل 3- FEMA- 101SLG سازمان مدیریت منابع.............................................................. 10

شکل 4- اینوسفر – نمای کلی................................................................................................. 11

شکل 5- نمای کلی سیستم مدیریت بحران................................................................................ 13

شکل6- ساختار الگوریتم بازپخت شبیه سازی شده..................................................................... 19

شکل 7- ساختار الگوریتم ژنتیک............................................................................................. 20

شکل 8- روند الگوریتم انشعاب و کران.................................................................................... 22

 

فصل اول - مقدمه

مسئله مدیریت بحران در سالهای اخیر اهمیت شایانی یافته است . با توسعه محیطهای شهری ،هنگام وقوع یک بحران خطرات جانی و مالی زیادی افراد شهر را تهدید می کند .به این دلیل ایجاد سیستم مدیریت بحران مؤثر و سازمان یافته بسیار ضروری است. هر بحران شامل چندین حادثه با درخواست تعداد معینی واحد اورژانسی است .وضعیت نابهنجار زمانی به وجود می آید که مسئله کمبود منابع و رقابت برای منابع مطرح می شود.با اینکه هر بحران درجه شدت متفاوتی دارد، اما واکنش مناسب به درخواست هر بحران بسیار ضروری است. با تخصیص واحدهای اورژانسی به حوادث به طور خودکار ، گام بلندی در جهت حذف خطاهای بشری برداشته شده است .

در این پروژه روشهای هوش ازدحامی برای تخصیص تعداد بهینه از منابع در محیطی با چند بحران پیشنهاد شده است. این روشها تکنیکهای جدیدی در مدل کردن روند بحرانی با جمعیتی از عاملها و تخصیص منابع است به طوری که همه بحرانها بتوانند از منابع موردنظرشان استفاده کنند. هوش ازدحامی سیستمی است متشکل از تعداد زیادی افراد که با یک کنترل نا متمرکز و خودسامانده متعادل و هماهنگ می شوند . هوش ازدحامی ، منبع الهامی جهت توسعه سیاست های تخصیص گردش کار است. الگوریتم هایی که از این رفتار الهام میگیرند به طور موفقیت آمیزی جهت کاهش زمان های تنظیم شده و زمان های عملکرد در تولید زمان بندی صنعتی به کار میرود .

در این پروژه روشهایی برای بهینه سازی تخصیص منابع به وقایع بحرانی مختلف با توجه به محدودیتهایی همچون دسترس پذیری منابع ، وضعیت بحرانی وقایع، تعداد منابع خواسته شده و غیره ارائه شده است. روش پیشنهادی به سمت مدیریت رخداد وقایع بحرانی به طور همزمان در یک محیط از پیش تعریف شده خاص با مراکز تخصیص منبع تعیین شده در همان محل پیش می رود. هدف افزایش بهره وری واحدهای واکنش اضطراری به همراه کاهش زمانهای واکنش است. هدف اصلی از تخصیص خدمات اورژانسی ، بیشینه سازی کارایی واحدهای واکنش اضطراری در دسترس و موجود و کمینه سازی زمان واکنش برای کاهش آثار یک یا چند واقعه است.

آژانس های مختلفی در این زمینه تاسیس شده است از آن جمله آژانس مدیریت اورژانسی فدرال(FEMA)[1] است. همچنین سیستمهایی برای نظارت و تخفیف آثار حوادث طراحی شده است مانند سیستم دریافت و پاسخ (اینفوسفر)[2] و سیستم مدیریت بحران (CMS)[3].

الگوریتم های زیادی به همراه تعمیمشان برای رسیدن به راه حل های بهینه مسئله تخصیص منبع پیشنهاد شده است. الگوریتم ژنتیک ، تئوری بازیها ، الگوریتم های پویا و... از آن دسته اند.

عملیات نجات روبوکاپ موضوع تعدادی از پیاده سازی های عملی و سودمند است. عملیات نجات روبوکاپ یک محیط شبیه سازی شده برای برنامه ریزی حادثه شامل عاملهای متعدد است.در فصل های بعد به مسائل گفته شده پرداخته می شود.

 

[1] Federal Emergency Management Agency

 

[2] Infosphere

 

[3] Crisis Management System

 

فصل دوم-مدیریت بحران

2-1-مقدمه

در طی چند دههاخیر مدیریت بحران به یک مسئله چندوجهی و پیچیده تبدیل شده است. ماهیت یک بحران یا حادثه از حوادث طبیعی مثل طوفانها و زمین لرزه ها تا حوادث ساخت بشر مانند سقوط هواپیماها، حوادث تروریستی، اعمال عمدی، تخریب انبوه، حوادث صنعتی و غیره متغیر است.

با توسعه و گسترش جوامع شهری ، هنگام وقوع یک بحران خطرات جانی و مالی زیادی افراد شهر را تهدید می کند .به این دلیل ایجاد سیستم مدیریت بحران مؤثر و سازمان یافته بسیار ضروری است.

پروسه مدیریت بحران شامل مراحل تحلیل خطر، دریافت ، واکنش ، نظارت و تخفیف آثار یک بحران می باشد.

در صورت وقوع حوادث متعدد در یک محیط شهری با مسئله مدیریت و تخصیص منابع مواجه خواهیم شد . در این فصل روشهایی برای بهینه سازی تخصیص منابع به وقایع بحرانی مختلف با توجه به محدودیتهایی همچون دسترس پذیری منابع ، وضعیت بحرانی وقایع، تعداد منابع خواسته شده و غیره ارائه شده است. روش پیشنهادی به سمت مدیریت رخداد وقایع بحرانی به طور همزمان در یک محیط از پیش تعریف شده خاص با مراکز تخصیص منبع تعیین شده در همان محل پیش می رود. هدف از مدیریت بحران افزایش بهره وری واحدهای اورژانسی و نیز کاهش زمانهای واکنش است.

2-2-مدیریت بحران

هر جامعه به یک آرایش از واحدهای واکنش اضطراری برای رسیدگی به وقایع بحرانی گوناگون نیاز دارد. مدیریت بحران یعنی ارسال به موقع منابع مورد نیاز به مناطق بحران زده[1].

پیچیدگی این کار از ناهماهنگی واحدهای واکنش اضطراری مانند ماشینهای آتش نشانی ، آمبولانسها و ماشینهای پلیس ناشی می شود.

بعلاوه این واحدها در یک ناحیه وسیع و کنترل شده توسط سازمانهای متعدد توزیع شده است. هر بحران در شدت، درخواست تعداد و نوع منابع و موقعیت منحصر بفرد است. در صورت وقوع حوادث همزمان متعدد ، تعیین شدت هر بحران و تخصیص تعداد بهینه و نوع مناسب واحدهای اورژانسی به هر موقعیت مهم و حیاتی است. بسته به مکان و ماهیت بحران ممکن است درخواستهای اضافی برای واحدهای اضطراری جهت جلوگیری از بدتر شدن یک وضعیت وجود داشته باشد. اگرچه بعضی وقایع ممکن است بحرانی تر از بقیه باشد اما همه آنها نیاز دارند برای جلوگیری از وقوع حوادث و خسارت بیشتر فوراً کمک شوند. هدف اصلی از تخصیص خدمات اورژانسی ، بیشینه سازی کارایی واحدهای واکنش اضطراری در دسترس و موجود و کمینه سازی زمان واکنش برای کاهش آثار یک یا چند واقعه است. شکل 1روند مساعدت با درک بهتر موقعیت را نشان می دهد.

 

 

 

 

 

 

 

 

 

 

 

 

 

شکل 1-وقوع چند بحران هم زمان در یک ناحیه شهری

 

 

فرض کنید یک روند بحران فرضی در یک شهر در حال وقوع است:

ü یک هواپیما در هنگام فرود در فرودگاه سقوط می کند، هواپیمای مسافربری کوچک با 30 تا 35 نفر شامل کارکنان هواپیما. حادثه سقوط بر 2 تا 3 هواپیمای مستقر در فرودگاه نیز تأثیر می گذارد.

ü آپارتمانی در طبقه ششم یک برج بلند آتش می گیردو افرادی در آپارتمان گرفتار می شوند. آتش سوزی کم کم در دیگر آپارتمانهای همان طبقه و طبقه بالایی منتشر می شود.

ü یک تظاهرات در جلوی ساختمان شهر به شورش تبدیل شده است. چند نفر از شورشگران خشمگین شده اند و اشیاء شعله ور به اطراف پرتاب می کنند.

هر کدام از وقایع بالا به عنوان یک بحران تلقی می شوند ، اگرچه هریک در شدت وضعیت بحرانی و تعداد منابع مورد نیازش متفاوت است. سقوط هواپیما بیشترین اولویت را دارد. چون سوخت هواپیماها بسیار آتشگیر است و سایر هواپیماها نیز در معرض خطر هستند بنابراین در حادثه هواپیماها احتمال تلفات و وخامت اوضاع بیشتر است. باید انفجار قبل از اینکه به دیگر هواپیماها سرایت کند و سبب خسارت بیشتری شود کنترل شود. آتش سوزی در اولویت بعدی است و باید قبل از اینکه همه ساختمان را از بین ببرد و سبب خسارت جانی و مالی بیشتری شود کنترل شود. شورش در اولویت آخر قرار دارد. در این وضعیت سه نوع از منابع ملاحظه می شود. آمبولانسها از بیمارستانها و ماشینهای پلیس از ایستگاه پلیس و ماشینهای آتش نشانی از ساختمان آتش نشانی. سقوط هواپیما و صحنه آتش سوزی به ماشینهای آتش نشانی و آمبولانسها نیاز دارند. هر دو موقعیت ممکن است به تعدادی ماشین پلیس برای کنترل شلوغی و برقراری قانون و نظم و جلوگیری از فرار شورشگران نیز احتیاج داشته باشند. همچنین به تعدادی آمبولانس برای تلفات شورش و تعدادی ماشین آتش نشانی برای کنترل آتش سوزی توسط شورشگران نیاز است و عاملهای زیادی مانند دسترس پذیری، فاصله، شرایط ترافیکی و غیره تعیین می کند چه تعداد منابع و از کدام مرکز منبع به مکانهای بحرانی فرستاده شود. به طور قطع به تعداد کافی آمبولانس و ماشین آتش نشانی در مقایسه با درخواستهایی که از طرف موقعیتهای بحرانی، به مرکز رسیده وجود ندارد. بنابراین بسیار مهم است که یک تخصیص بهینه از منابع انجام شودزیرا که بهره برداری کمتر یا بیشتر از منابع می تواند در حفظ جان مردم تاثیرگذار باشد. تخصیص باید با عامل هایی مانند شرایط بحرانی حوادث، درخواست و دسترس پذیری منابع، فاصله و تعداد مراکز منبع سنجیده شود.

2-3-آژانسهای مدیریت بحران

چندین آژانس تاسیس شده است و سیستمهایی برای نظارت و تخفیف آثار حوادث طراحی شده است. بعضی از ویژگیهای برجسته این آژانسها و سیستم ها مورد بررسی قرار می گیرد.

2-3-1- آژانس مدیریت اضطراری فدرال (FEMA)

این آژانس، که پیش از این مستقل بوده و در مارچ 2003 بخشی از سازمان جدید امنیت سرزمین ملی شد وظیفه پاسخگویی، برنامه ریزی ، بازیابی و تخفیف حوادث را دارد. نقطه آغاز FEMA در تصویب نامه کنگره ای 1803 است که یک بخش از قانون مدیریت حوادث جهت مساعدت به یک شهر را به دنبال یک آتش سوزی وسیع فراهم کرد. در قرن اخیر قانون موقت بیشتر از صد بار در واکنش به طوفانها زمین لرزه ها سیلها و دیگر حوادث طبیعی تصویب شده بود. در طی چند سال گذشته تاسیسات نیروی هسته ای، انتقال مواد پرخطر و وظایف دفاع داخلی نیز بر ترکیب پیچیدگی مدیریت اضطراری این آژانس افزوده شده است.

شکل 2 یک قطعه از راهنمایی محلی و وضعیتی 101 را نشان می دهد: راهنمایی برنامه ریزی عملیاتهای اورژانسی چند بحران . اینها رهنمودهایی برای آمادگی اورژانسی است. بخش تحقیق وظایف مربوط به تخصیص منبع را نشان می دهد. هر راه حل پیشنهادی به اطلاعات کاملی درباره پایگاه منبع، نقشه برداری، حوزه قضایی و طبقه بندی اولویت نیاز دارد.

تحقیق

توسعه

معتبرسازی

حمایت و پشتیبانی

ü بررسی قانون طرحها راهنمایی و توافق کمک دو جانبه ü تعیین پایگاه منبع ü هدایت تحلیلهای ریسکی/خطری ü ثبت اشکال خاص محیط برنامه ریزی

 

 

 

 

 

 

 

شکل 2- FEMA– 101SLG فرایند برنامه ریزی

 

طبق سالهای مالی برنامه راهبردی FEMA از 2003 تا 2008:

ü بحران/ حادثه: عمومأ تعریف شده در برداشتن حوادث و اضطراراتی را که ممکن است توسط طبیعت یا وقایع ساخت بشر به وجود آید.

ü واکنش: عملیات اورژانسی هدایت کننده به حفظ جانها و اموال شامل استقرار منابع و تجهیزات اورژانسی تخلیه تلفات تأمین غذا آب پناهگاه و مراقبت پزشکی با توجه به نیاز و ارائه خدمات عمومی و حیاتی

ü بازیابی: بازسازی جوامع اعم از فردی، شغلی و زیربنای دولتی می تواند روی آنها اثر گذاشته آنها را به حالت عادی برگرداند و در مقابل خطرات آینده پشتیبانی شود.

مدیر منبع

تحلیل نیازها: - دریافت درخواستها - اولویت بندی وقایع - تحویل درخواستها - پیگیری وضعیت درخواستها - گزارش وضعیت منبع به مدیر منبع

هماهنگی تدارکات: - تدارک پرسنل و واحدها - هماهنگی حمل و نقل

هماهنگی: - هماهنگی مسیریابی پذیرش ذخیره و بررسی موجودی انبار

 

 

 

 

 

 

 

 

 

شکل 3- FEMA- 101SLG سازمان مدیریت منابع

 

بعد از جمع آوری اطلاعات منابع و خطرات احتمالی، یک سیستم به رهنمودهایی درباره توزیع منابع نیاز دارد. شکل 3- طرح کلی مختصری از سازمان مدیریت منبع را ارائه می دهد. بخش تحلیل نیازها در این شکل از جهت به روز رسانی های منبع در هر لحظه، اولویت دهی به وقایع و ارسال منابع به این کار مرتبط است.

 

 

2-3-2-اینفوسفر[1]- سیستم دریافت و پاسخ

پروژهاینفوسفر کالتچ به سیستم های مرکب یا سیستم های ساخته شده از اجزای متقابل اختصاص دارد. یکی از کاربردهای این پروژه یک سیستم دریافت و پاسخ را در بر می گیرد. هدف اساسی سیستم نگهداری یک مخزن اطلاعات از منابع متعدد و تنظیم آنها به یک لغت استاندارد شده است.

شرایط معینی تعیین می کنند که اعلام خطرهای سیستم تولید شود. سیستم بر اطلاعات رسیده از سازمانهای مختلف نظارت می کند و هنگامی که شرط معینی برقرار شد اعلام خطرها به سمت مقصد فرستاده می شوند. سیستم می تواند برای کاربردهای مشخصی برنامه ریزی شود مثلاً سیستم هواپیما وقتی که یک عیب فنی تجهیزاتی پیدا می کند به حالت دیگر تغییر وضعیت می دهد. منابع اطلاعاتی بازبینی شده برای کاربردهای خاص از جهات ظرفیت، سرعت، غیر یکنواختی و ماهیت توزیع شده وسیع است.

سیستم پیشنهاد شده بر مبنای تکرار خطاها ، زمان واکنش ، منابع محاسباتی به کار رفته، شفافیت و سهولت توافق ارزیابی شده است. شکل 4 نمای کلی از جریان کنترل سیستم پیشنهاد شده را ارائه می دهد.

ایجاد یک مجموعه از شرایط دریافت- پاسخ برای یک کاربرد

نظارت بر اطلاعات آژانسها برای یافتن تغییرات مهم در مقادیر اطاعات

تشخیص زمانی که شرایط خاص (اعلام خطر) برقرار می شود

انتشار اعلام خطرها به مقصدها

 

 

 

شکل 4- اینفوسفر – نمای کلی

 

2-3-3-سیستم مدیریت بحران (CMS)[2]

CMS یک نرم افزار مدیریت بحران قدرتمند است که توسط شرکای علمی کاربردی تهیه و ثبت شده است. CMS به عنوان ابزاری برای مدیران واکنش اضطراری دریایی برای مدلسازی ضربات و آثار زیستی ریزش یا یک حادثه طراحی شده است. CMS همچنین می تواند برای آموزش و شبیه سازی تمرینات، تحلیل مزایای هزینه ای و تسهیل واکنش بلادرنگ در حوادث دریایی به کار برده شود. CMS برای ریزش روغن و مواد شیمیایی ، مأموریت جستجو و نجات حوادث هسته ای و اورژانسی دریایی طراحی شده است. همه ماشینهای بخش CMS به یک پایگاه اطلاعاتی منبع واحد متصل شده اند و توانایی دستیابی فوری به اطلاعات منبع را دارند. CMS به یک سیستم اطلاعات جغرافیایی (GIS)² برای دریافت اطلاعات محیطی لحظه ای مجهز شده است. CMS برای مدیریت و توزیع اطلاعات سازمان جهت رسیدن به واکنش و بازیابی به کار برده می شود.

مدیریت چند بحران یک مسئله پیچیده شامل دریافت ، واکنش و بازیابی از حوادث است. تهیه مقدماتی سودمند در مواجهه با اتفاقات آینده برای فراهم کردن سطحی بهتر از آمادگی و واکنش به حوادث در جهت کاهش تلفات جانی و مالی بسیار مهم است. در بخش قبل سیستمها و آژانسهای طراحی شده برای اصلاح و افزایش توانایی مدیران واکنش اضطراری در جهت ایجاد تصمیمات مدیریت بحران موثر معرفی شد. ابتدا پروتکلها و رهنمودهایی (مانند FEMA) برای تحلیل خطر، کاوش پایگاه منبع و هماهنگی کارکنان و واحدهای منبع ایجاد شدند. بعد از آن مکانیزمهای اعلام خطر (مانند اینفوسفر) جهت نظارت بر حوادث و انجام به روز رسانیهای لحظه ای در آنها و منابع فرستاده شده برای تخفیف آثار آنها هستند. زمانیکه کارهای زیادی در جهت جمع آوری اطلاعات مربوط به منابع و طبقه بندی حوادث انجام می شد، کار قابل توجهی در جهت مکانیزه کردن تخصیص منابع به وضعیتهای بحرانی وجود نداشت. تخصیص واقعی منابع به صورت دستی بر پایه راهنماییهای از پیش تعریف شده و پروتکلها و اطلاعات لحظه ای جمع آوری شده از محل وقوع انجام شده است و در معرض خطای انسانی است.

این پروژه مدلی پیشنهاد می کند که همان اطلاعات را به کار می برد و راهبردهای تخصیص امکان پذیری را بر می شمرد و یک مجموعه بهینه از راهبردهای مدیریت هر بحران را تعیین می کند. کاربردهای پیشنهاد شده بر پایه یک الگوریتم بهینه است برای دریافت بهترین تخصیص ممکن که برای همه مکانهای بحرانی سودمند است.شکل 5 نمای کلی از سیستم مدیریت بحران را نشان می دهد.

 

 

 

مکانیزم اعلام خطر بحران مانند « سیستم دریافت و پاسخ »

تشخیص خطر بحران

تخفیف بحران و گسترش منابع

نظارت بر گسترش بحران و دیگر وقایع ممکن مانند CMS

بازیابی و بهبود

 

 

 

 

 

 

 

شکل 5- نمای کلی سیستم مدیریت بحران

 

2-4-انواع روشهای الگوریتمی تخصیص منابع

چندین راه حل الگوریتمی و تعمیمشان برای رسیدن به راه حل های بهینه مسئله تخصیص منبع پیشنهاد شده است. در این بخش بعضی الگوریتمهای کاربردی برای حل مسئله تخصیص منبع بررسی می شود. اگرچه روشهای الگوریتمی برای مسائل تخصیص منبع گسسته و پیوسته بررسی می شود اما الگوریتمهای گسسته به خاطر ارتباطشان با این پروژه اهمیت داده می شود.

2-4-1-برنامه نویسی پویا:

برنامه نویسی پویا برای مسائل بهینه سازی به کار می رود زمانی که مجموعه ای از انتخابها برای رسیدن به یک راه حل بهینه وجود دارد. ممکن است چندین راه حل برای رسیدن به مقدار بهینه وجود داشته باشد. الگوریتم برنامه نویسی پویا می تواند در چهار مرحله طبقه بندی شود:

• تعریف ساختار راه حل بهینه
• تعریف بازگشتی راه حل بهینه
• محاسبه راه حل بهینه
• محاسبه راه حل بهینه در یک روش پایین به بالا
• تهیه راه حل بهینه با استفاده از اطلاعات بدست آمده از مراحل قبلی

فرمول بندی برنامه نویسی پویا برای مسئله تخصیص کار چند عامله با زمان بهینه انجام شده است. m کار به n عامل اختصاص داده شده است و m<n و هر عامل فقط می تواند یک کار را انجام دهد. یک الگوریتم تخصیص کار برای یک تخصیص کار بهینه سراسری، بر پایه یک مسئله بازگشتی خاص وابسته به اصل بهینه سازی بدست آمده است. پس از آن، برنامه نویسی پویا به سبک الگوریتم تخصیص کار زمان بهینه ساخته شده است ، از اینرو هر مرحله الگوریتم بر پایه بازگشت به عقب زودتر است.

برنامه نویسی پویا شبیه به مسئله تقسیم و حل است. اما روش اخیر برای مواقعی که زیر مسائل مشترکی وجود دارد مناسب نیست چون آنها را بطور متناوب حل می کند.

برنامه نویسی پویا هر زیر مسئله را فقط یکبار حل می کند و آنرا در یک جدول ذخیره می کند و به این وسیله از محاسبه مجدد زیر برنامه ای که قبلاً مواجه شده جلوگیری می کند. معایب برنامه نویسی پویا این است که هر وقت برای هر مسئله بهینه سازی به کار رفته است و چندین متغیر وضعیت وجود دارد که هر کدام از آنها مراحل مجزای بزرگی دارند، از نظر ابعادی بسیار گسترده می شود.متغیرهای وضعیت باید با تعداد واحدهای هر مرکز منبع منطبق باشد. همچنین، هزینه محاسباتی الگوریتم پیشنهادی به سرعت با تعداد عاملهایی که موجب غیرعملی شدن آن برای تعداد زیادی از عاملها می شود، افزایش می یابد.

2-4-2-برنامه نویسی عدد صحیح

مسائل بهینه سازی زیادی می تواند به عنوان مسائل برنامه نویسی خطی یا غیرخطی بیان شود. یک برنامه خطی مسئله ای است که به صورت زیر بیان می شود:

Minimize Cx

Subject to Ax=b x0

که x یک بردار از متغیرهایی است که باید حل شود و A ماتریس ضرایب، و c و b بردارهای ضرایب معلوم اند. Cx به تابع هدف فرستاده شده است و عبارت Ax=b یک محدودیت است . یک برنامه غیرخطی مسئله ای است به فرم

Minimize f(x)

Subject to g_i(x)=0 i=1,..,m m0

h_j(x)0 j=m+1,…,n

f(x) یک تابع هدف شامل چندین متغیر است و دو تابع دیگر محدودیتها هستند. اگر لازم است متغیرهای نامعلوم اعداد صحیح باشند، چنانچه در این مورد لازم است، مسئله به یک برنامه نویسی عدد صحیح ارجاع داده می شود. اگر مسئله فقط به بعضی از متغیرها برای گرفتن مقادیر صحیح نیاز دارد، برنامه نویسی عدد صحیح مختلط (مرکب) نامیده می شود و البته واقعیت این است که برای حل کردن سخت تر است.

روشهای برنامه نویسی عدد صحیح می تواند روی یک محدوده قابل توجه از کاربردها و اندازه های مسئله به کار رود. برنامه نویسی خطی عدد صحیح برای اصلاح راندمان پهنای باند شبکه ها با استفاده از الگوریتم حفاظت بخش به کار می رود. برنامه نویسی خطی عدد صحیح برای دستیابی به یک تخصیص بهینه ثباتها در پردازنده های همه منظوره و سیستم های کار گذاشته شده به کار می رود. اگر چه روشهای برنامه نویسی عدد صحیح برای راه حل های بهینه شناخته شده است، در هر دو کاربرد بالا تشخیص داده شده است که این روشها می توانند برای شبکه با اندازه متوسط، نه بزرگ (در مورد اول) و زمانهای حل کوتاه (در مورد دوم) به کار روند.

2-4-3-روش ضرب کننده لاگرانژ:

در مسائل بهینه سازی ریاضی، ضرب کننده های لاگرانژ در مسائل با محدودیتها به کار برده می شود.

آنها برای یافتن حداکثر و حداقل تابع چند متغیری دارای محدودیت به کار می رود:

Optimize f(x,y)

Subject to g(x,y)=0

لاگرانژ به صورت زیر نوشته می شود:

L=f(x,y)+g(x,y)

که یک ثابت به نام ضرب کننده لاگرانژ است. طبق روش ضرب کننده لاگرانژ، شرایط همزمان زیر وجود دارد:

()_x=0 ( ) _y=0

هدف یافتن ماکزیمم و مینیمم مقادیر بدست آمده از f در طول منحنی محدودیت روی نقاط g(x,y)=0 است. روش لاگرانژ روی همه متغیرها و محدودیتها به یک روش متقارن عمل می کند بنابراین مسائل با متغیرها و محدودیتهای زیاد می تواند به سادگی سازمان دهی شود . متدلوژی لاگرانژی برای زمانبندی و تخصیص منابع در یک واحد ساخت به کار می رود . هدف به کار گیری مؤثر منابع محدود برای رویارویی با نیازهای متقاضی پویا است. مراکز تولید ، یک سیستم ساخت قابل تغییر را با به کار گیری آرایشهای تولیدی برای ساده سازی خطوط روند تولید و افزایش بازدهی به کار می برند . زمانبندی برای تصمیم گیری زمان ساخت یک سلول (المان) برای تعداد زیادی تولید و تعداد ماشینها برای تخصیص به سلول به کار می رود . این مدل از تخفیف لاگرانژ استفاده می کند و یک تابع دوتایی را به وسیله کاهش پیچیدگی محدودیتها با ضرب کننده های لاگرانژ می سازد.

مسئله اصلی به زیر مسائلی که آسانتر حل می شوند تقسیم شده است . این مدل برنامه هایی با 16 تا 29 درصد بهینگی را تولید می کند . روش مشابه دیگر برای بهینه سازی تخصیص منابع در یک محیط محاسبه توزیع شده ، استفاده از تخفیف لاگرانژ و روشهای تابع گرادیان است .ملاحظه می شود که راه حل بهینه در یک تکرار متناوب بدون همگرایی حاصل می شود . همچنین راه حلهای بالا در زیر مسائل عملی نیستند و ابتکارات دیگری برای رسیدن به زمانبندی های عملی به کار رفته است .

2-4-4-باز پخت شبیه سازی شده

این الگوریتم بر پایه یافتن پیکربندی تعادلی میان مجموعه ای از اتمها در یک دمای داده شده در یک فضای بزرگ است. در سال 1973 ، پینکاس یک تناسب بین این الگوریتم و کمینه سازی ریاضی ترسیم کرد . این کار به عنوان یک تکنیک بهینه سازی برای مسائل ترکیبی پیشنهاد شده بود . بازپخت شبیه سازی شده یک تکنیک جستجوی تصادفی است با این مزیت که در مینیمم محلی نمی افتد . این روش تغییراتی را که سبب کاهش یا افزایش تابع هدف f می شود می پذیرد . تغییر افزایشی در احتمال P اثر میگذارد :

 

 

t یک افزایش در f است و T یک پارامتر کنترلی وابسته به دمای سیستم است. دمای اولیه T₀ اثر مهمی بر اجرای الگوریتم دارد . الگوریتم به یک برنامه بازپخت مسئله خاص شامل دمای اولیه و قواعد کاهش آن به عنوان نتایج جستجو نیاز دارد .

شکل 6 ساختار یک الگوریتم بازپخت شبیه سازی شده را نشان میدهد . یکی از مسائل مهم در اجرای بازپخت شبیه سازی شده واقع شدن در دشواری ترسیم تناسب بین T و پارامتر مستقل در مسئله است . بعلاوه اینکه نیفتادن در مینیمم محلی به انتخاب زمانبندی بازپخت ، تعداد تکرارهای انجام شده برای هر دما و میزان کاهش دما در فرآیند خنک سازی بستگی دارد.

 

 

 

شروع

دادن ورودی و آزمایش راه حل اولیه

T=T0 تعیین مقدار اولیه

تولید و آزمایش راه حل جدید

پذیرش راه حل جدید؟ ؟

به روز رسانی موجودی

تنظیم دما

پایان جستجو؟ ؟؟؟؟؟

پایان

خیر

بلی

بلی

خیر

 

 

 

 

 

 

 

 

 

 

 

شکل6- ساختار الگوریتم بازپخت شبیه سازی شده

2-4-5-الگوریتم ژنتیک

در سال 1975 الحاق اصول تکامل تدریجی روندهای بهینه سازی به طور رسمی انجام شد . برای به کارگیری یک الگوریتم ژنتیک نیاز به بیان راه حلی به عنوان یک ژنوم (یا کروموزوم) است. الگوریتم یک جمعیت اولیه را به عنوان ورودی می گیرد و عملگرهای ژنتیکی (جهش و برش ) را برای استنتاج و یافتن یک راه حل بهینه به کار می برد. مراحل اصلی به کارگیری الگوریتم های ژنتیک در مسائل زمان واقعی به صورت زیر است :

1- تعیین تابع هدف

2- بدست آوردن نمایش ژنتیکی راه حل

3- تعیین عملگرهای ژنتیکی

بازده الگوریتم ژنتیک به پارامترهای کنترلی وابسته است:

- جمعیت اولیه

- اندازه جمعیت

- احتمال برش P_c

- احتمال جهش P_m

شروع

تولید جمعیت تصادفی از n کروموزوم

ارزیابی برازندگی f(x) از هر کروموزوم

ایجاد یک جمعیت جدید با استفاده از عملگرهای انتخاب ، برش ، جهش و پذیرش

جایگزینی جمعیت فعلی با جمعیت جدید

آیا شرایط خاتمه برقرار شده؟

بهترین راه حل جمعیت را باز گردان

پایان

خیر

بلی

الگوریتم های ژنتیک از دو جهت شبیه به باز پخت شبیه سازی شده است ، یکی در به کارگیری قوانین انتقال احتمالی و دیگری در به کار گیری اطلاعات تابع هدف و نه مشتقات .الگوریتم ژنتیک اگر چه از نظر محاسباتی گران است اما به راحتی می تواند با تکامل تدریجی تابع هدف شبیه سازی شود و محدودیتها می توانند برای همه جمعیت در یک زمان اعمال شود .

 

 

 

 

 

 

 

 

 

شکل 7- ساختار الگوریتم ژنتیک

2-4-6- انشعاب و کران

انشعاب و کران الگوریتم دیگری است که برای حل مسائل بهینه سازی استفاده می شود .این روش همه فضای راه حل را برای بهترین راه حل جستجو می کند .همچنانکه تعداد راه حلهای ممکن به صورت نمایی افزایش می یابد شمارش همه آنها غیرممکن می شود از اینرو کرانهایی برای بهینه شدن تابع استفاده می شود . این الگوریتم سه بخش اصلی را شامل می شود :

- تابع محدودکننده برای تعیین کران پایین برای بهترین راه حل در زیر فضای راه حل داده شده

- روش تعیین و تحلیل زیر فضای راه حل بعدی

اگر زیر فضا بعد از تحلیل نتواند کران و محدودیت ایجاد کند قانون انشعاب زیر فضا را مجدداً به دو یا چند زیر فضا تقسیم می کند .

- اجرای الگوریتم انشعاب و کران به درجه بزرگی فضای جستجوی اولیه ورودی به الگوریتم وابسته است.

اگر اندازه هر زیر فضای تولید شده کوچکتر از اصلی باشد همگرا می شود .الگوریتم انشعاب و کران برای مسائل بهینه سازی پیوسته و گسسته مطلوب است اما به حافظه زیادی نیاز دارد .

2-4-7- الگوریتم حریص

الگوریتم حریص الگوریتمی است که حل مسئله ابتکاری ایجاد یک انتخاب بهینه محلی را در جهت رسیدن به راه حل بهینه سراسری دنبال می کند . الگوریتم های حریص همیشه راه حلهای بهینه تولید نمی کنند زیرا که همه راه حلهای ممکن از یک فضای جستجو را به طور کامل آزمایش نمی کنند. عناصر اساسی یک الگوریتم حریص به صورت زیر است :

- فضای راه حل از جائیکه راه حل ایجاد شده

- تابع انتخاب برای گزینش بهترین عنصر بعدی برای افزودن به راه حل

- تابع امکانپذیری برای بررسی شایستگی عنصر برای افزودن به راه حل

- تابع هدف برای محاسبه مقدار ( کامل یا جزئی ) راه حل به دست آمده

- تابع راه حل برای تعیین اینکه راه حل کامل حاصل شده

الگوریتم های حریص به ندرت برای به دست آوردن راه حلهای بهینه استفاده می شوند و معمولاًزمینه یک روش ابتکاری را تشکیل می دهند . اگر هم مسائلی باشند که به روش حریص حل شوند بهینه سازی آنها غیر بدیهی است . روشهای حریص به خاطر عدم اطمینان در تهیه راه حلهای بهینه کمتر استفاده می شوند .

 

 

 

 

 

 

 

 

 

شکل 8- روند الگوریتم انشعاب و کران

2-4-8- جستجوی تابو

در سال 1977 ، فرد گلاور روش حرکت میان فضای راه حل و به کارگیری تکنیکهای حافظه برای جلوگیری از دورهای متناوب را ارائه کرد . الگوریتم حرکتها را در لیست تابو ثبت می کند و اگر راه حل را به نقطه ای از فضای راه حل که قبلاً آنرا دیده بود ببرد ، آنرا جریمه می کند . از اینرو از افتادن در چرخه ها جلوگیری می کند . جستجوی تابو یک تکنیک استنتاج و جستجوی گسترده بهینه سازی است . اگرچه جستجوی تابو راه حلهای برتر و قابل مقایسه برای بهینه سازی مسائل ارائه می کند اما بهینگی را تضمین نمی کند . همچنین ایجاد لیست تابو برای ثبت یک رکورد از حرکتها ابتکاری است .

2-4-9- تئوری بازیها

تئوری بازیها وسیله ای برای مدل کردن و تحلیل تضاد و هماهنگی میان نشانگرهای تصمیم به نام بازیکن است . یک وضعیت زمانی شکل می گیرد که نشانگرهای تصمیم متعدد بااهداف مختلف روی یک سیستم اثر بگذارند یا منابع را تقسیم کنند . تئوری بازیها در سال 1944 با انتشار مقاله «تئوری بازیها و رفتار اقتصادی » توسط ون نیومن و مورگانسترن رسمی شده بود . تئوری بازیها یک چارچوب طبیعی برای مدل کردن روند بحران تأمین می کند. بازیها به سبب ماهیت رقابتی بازیکنان می توانند بحرانهایی را که برای تعداد محدودی از واحدهای اورژانسی رقابت می کنند را شبیه سازی کنند .

بازیها یک مجموعه محدود از عملیات یا راهبردهای تخصیص در دسترس دارند.عمل انتخاب به هر ترکیبی از راهبردها و به هر بحران وابسته است. راهبرد انتخاب شده به وسیله یک بحران به سه پارامتر وابسته است :

- فضای راهبردی که مجموعه راهبردها (تخصیصها)ی در دسترس برای بحران را شامل می شود.

- اطلاعات دیگر بحران ها ( اولویت ، فاصله از مرکز)

- تابع نتیجه یا بهره وری که رضایت یک کاربر از نتیجه را تأمین می کند .

هر بازیکن برای افزایش بهره اش در بازی تلاش می کند . یک جنبه مهم از تئوری بازیها این است که هر تصمیم بازیکن بر پایه تصمیم دیگر بازیکنان است از اینرو هر بازیکن می تواند بهره اش را نسبت به دیگر بازیکنان بهینه کند.ماهیت رقابتی بازی و وابستگی تابع هدف هر بازیکن به تصمیم دیگر بازیکنان ،به راهبرد تخصیص منبع برای دریافت تابع هدف دیگر بازیکنان نیاز دارد .

2-5-عملیات نجات روبوکاپ[2]

جهت آرایش گروهی بزرگ در مسئله نجات از حادثه مدلی ارائه شده است. در این مدل تیمی با عاملهای متعدد آرایش یافته و تخصیص کار از طریق ارتباط ضمنی بین عاملها انجام می شود. عاملهای هوشمند[3] در سراسر ناحیه کار بطور پویا قرار گرفته اند و فرایند ارتباطی بین عاملهای کار را میانجی گری می کنند. عملیات تخصیص کار و وضعیت جاری انجام می شود. آرایش تیم بر اساس نیرو و نوع کارها انجام می شود. تیمهای بزرگ با به کارگیری مکانیزمهای کنترل و ارتباط نامتمرکز (الهام شده توسط رفتارهای جمعی زیستی) تشکیل می شوند. در یک عملیات نجات که محیط در آن بطور پویا تغییر می کند روش کاربردی به هماهنگی کارهای متعددی نیازمند است. در یک محیط پویا برای تخصیص تیمهای عاملهای ناهمگن و تکمیل کارها در یک بازه زمانی معقول اطلاعات کمی وجود دارد. برای نجات از حادثه به هماهنگی میان تعداد زیادی عامل با تواناییهای متفاوت نیاز است. این مدل را می توان برای محیط های مشابه مانند شناسایی فضا و میدان جنگ درون شهری تعمیم داد. عملیات نجات روبوکاپ یک محیط شبیه سازی شده برای برنامه ریزی حادثه شامل عاملهای متعدد است[2]. محیط که می تواند یک محدوده شهری باشد متأثر از حوادثی مانند آتش یا زمین لرزه است. هدف این است که گروهی از عاملهای ناهمگن در انجام کارهایی مانند خاموش کردن آتش نجات انسانها و بازکردن راههای ارتباطی با هم همکاری کنند. این کار به خاطر معرفی چالشها در تشکیل تیمهای پویا از عاملهای ناهمگن در یک محیط متغیر جالب توجه است. نظریه هدایتگر ها که عاملهای ساکن هوشمندی هستند و بطور پویا در ناحیه کار توسط عاملهای متحرک قرار گرفته اند ارائه می شود. هر هدایتگر با میانجی گری ارتباط میان عاملهای متحرک، دستیابی به هدف را در ناحیه محلی اش هماهنگ می کند. فرض شده هدایتگر ها دامنه ارتباطی نسبتأ کوتاهی دارند و عاملهای متحرک فقط با عاملهای ناحیه خودشان ارتباط دارند. عاملهای متحرک عاملهای ساکن را مطابق با نیازهای کاری مختلف آن ناحیه به روز می کنند. این رویه تا زمانی پیش می رود که کنترل نامتمرکز توسط عاملهای ساکن وارد شود و به راهبردهای هماهنگی اجازه دهد در میان عاملهای در زمان واقعی شکل گیرند.

عملیات نجات روبوکاپ موضوع تعدادی از پیاده سازی های عملی و سودمند است. هدایتگر ها در تشکیل تیم میان عاملها وارد نمی شوند و فقط راهنمای حرکت هستند. این روش کاربرد هدایتگر های شبکه ای با هدایتگر های هوشمند و مستقل و راهنمای عاملهای اجرای کار. هدایتگر ها به طور پویا در دامنه کاری بعنوان عامل هماهنگی و کنترل نامتمرکز گسترش می یابند. هدف از به کارگیری عاملهای مختلف نجات تعداد زیادی از انسانها در کوتاهترین زمان ممکن است که هر کدام یک عملیات نجات نیاز دارد. عملیات نجات به هماهنگی عاملهای متعددی نیاز دارد. تعداد عاملهای مورد نیاز برای عملیات نجات به درجه خسارت بستگی دارد که توسط عاملها تعیین می شود وقتی برجهای پیام فرو بریزند کانالهای ارتباطی مسدود می شود و امکان کنترل مرکزی عملیات که شامل هزاران عامل است وجود ندارد.

2-5-1-ساختار سیستم:

ساختار کلی برای حوزه هایی شامل هماهنگی تعداد زیادی از عاملهای متحرک که هر کدام تخصص کاری مختلفی دارند و اجرای کارهای پیچیده در محیط متغیر طراحی شده است. کاوش فضا جستجوی مناطق وسیع مین جنگ درون شهری و عملیات نجات روبوکاپ مثالهایی از این محیطها هستند.

2-5-2-ساختار عاملها:

این مدل شامل عاملهای زیر است:

1- عاملهای متحرک ناهمگن یا عاملهای کار که باید انجام کارهای برآمده از محیط را هماهنگ کنند.

2- عاملهای ساکن (یا هدایتگر ها) که عاملهای کار را در ناحیه خاص راهنمایی می کنند.

عاملهای متحرک فقط با عاملهای ساکنی که در همسایگی سیگنالی خود هستند ارتباط دارند. عاملهای کار بین حوزه های کاری حرکت می کنند که می توانند موقعیت فعلی خود را محاسبه کنند.

 

 

 

عاملهای متحرک به بخشهای زیر تقسیم می شوند:

1- عاملهای جستجوی کلی که گیرنده های همه منظوره برای تعیین انسانها و وسایل و ساختمانهای خسارت دیده دارند و با عاملهای ساکن اطراف اهداف ناحیه با اطلاعات مکانی تقریبی ارتباط دارند.

2- عاملهای تأیید کار که گیرنده های دقیقی برای تخمین درجه خسارت و تعداد انسانهای افتاده در محل دارند آنها تعداد و نوع عاملهای نجات ورد نیاز برای عملیات را محاسبه می کند

عاملهای ساکن عاملهای تأیید کار را از جهت مکان تقریبی اهداف مورد جستجو کمک می کنند

3- عاملهای نجات که پیشگویی تولید شده توسط عاملهای تأیید کار را برای تشکیل تیم با تواناییهای لازم، استفاده می کند

بعد از اینکه نیروی تیم به حد کافی رسید عاملها برای نجات هدف حرکت می کنند.

4- عاملهای گسترش که تعداد هدایتگر ها را دارند. آنها در حوزه کار حرکت می کنند و از یک ملاک ساده برای تصمیم اینکه چه وقت عاملهای ساکن باید وارد شوند استفاده می کند اگر در هر نقطه ای از هدایتگر یک پیام منتشر دریافت نکنند یک هدایتگر را می فرستند (عامل سکن) که با مهر زمان فعلی و اطلاعات مکانی مقداردهی اولیه شده است. در غیر اینصورت آنها حرکت را ادامه می دهند. عاملهای ساکن یک هدایتگر شبکه ای با تواناییهای ارتباطی و محاسباتی هستند که می توانند در منطقه کار گسترش پیدا کنند. عاملهای ساکن سیگنالهایشان را در یک دامنه کوتاه منتشر می کنند با ارتباط با عاملهای کار که به پیام منتشر شده جواب می دهند

 

 

2-5-3-تشکیل تیم

تیم ها با توجه به ارتباط ضمنی بین عاملهای کاری با وساطت هدایتگر ها تشکیل شده اندحوزه کاری بطور پویا به تعدادی ناحیه کاری کوچکتر تقسیم می شود که هر ناحیه یک هدایتگر راهنما که اطلاعات ناحیه را نگهمیدارد دارد.اطلاعات از طریق ارتباط بین هدایتگر ها و عاملهای متحرک که ناحیه را سرکشی می کنند جمع آوری می شود. همچنین هدایتگر ها ارتباط منظم کارها را برقرار می کنند.

وقتی یک عامل به ناحیه اش وارد می شود سعی می کند مکانی را که ممکن است در آن برای انجام کار مخصوص به خودش مورد نیاز باشد پیدا کندبعضی کارها ممکن است با بیشتر از یک عامل سروکار داشته باشند در این حالت هدایتگر پیشنهاد می کند که عاملها برای جمع شدن تعداد مناسبی از نوع مشخص عاملها منتظر باشند.پس کنترل کننده های نامتمرکزی وجود دارد که اطلاعات محیط محلی را دارند و این اطلاعات را برای به کار گرفتن عاملهای کاری در تیم ها به کار می برند.

عاملهای کاری در ورود به یک ناحیه به دنبال کارهای مخصوص به خودشان می گردند. عاملهای جستجو در ناحیه به دنبال اهداف حرکت می کنند. وقتی یکی پیدا کردند با هدایتگر برای ثبت حضور هدف ارتباط برقرار می کنند.

سپس هدایتگر منتظر می شود تا یک عامل تأیید توان در موقعیت هدف را تخمین بزند وقتی یک عامل تأیید وارد یک ناحیه می شود هدایتگر مسیر به سمت مکان تقریبی هدف را راهنمایی می کند و عامل تأیید اطلاعات نیرو و مکان هدف را به هدایتگر می فرستد. مقدار نیرو برای تخمین تعداد عاملهای نجات مورد نیاز به کار می رود و هدایتگر لیست این تخمین ها را نگهداری می کند وقتی عامل نجات وارد ناحیه می شود حضورش را ثبت می کند هدف را محصور کرده و برای پیام از هدایتگر منتظر می شود زمانیکه عاملهای نجات کافی در ناحیه جمع شدند هدایتگر عاملها را برای حرکت به سمت هدف مطلع می کند و تیم عاملهای نجات کار نجات را انجام می دهندوقتی که یک عامل کار معینی ندارد در محیط حرکت می کند و به دنبال اهداف، دیگر نواحی را جستجو می کند.

 

[1] Infosphere

[2] Crisis Management System

[3] Beacon